/**
 * @author:gao
 * @date:2020/7/1
 * @time:10:26
 * @version:0.0.1
 * @description:none
 */

//718. 最长重复子数组,给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

//class Solution {
//    public int findLength(int[] A, int[] B) {
//        int lenA = A.length;
//        int lenB = B.length;
//        int[][] dp = new int[lenA][lenB];
//        int a = A[0];
//        int b = B[0];
//        if(a==b) dp[0][0] =1;
//        else  dp[0][0] = 0;
//        for(int i=1;i<lenB;i++){
//            if(a==B[i]||dp[0][i-1]==1) dp[0][i]=1;
//            else dp[0][i]=0;
//        }
//        for(int i=1;i<lenA;i++){
//            if(b==A[i]||dp[i-1][0]==1) dp[i][0]=1;
//            else dp[i][0]=0;
//        }
//        for(int i=1;i<lenA;i++){
//            for(int j=1;j<lenB;j++){
//                if(A[i]==B[j])dp[i][j]=dp[i-1][j-1]+1;
//                else dp[i][j] = Math.max(dp[i-1][j-1],Math.max(dp[i-1][j],dp[i][j-1]));
//            }
//        }
//        return dp[lenA-1][lenB-1];
//    }
//}


//dp,这种思路感觉跟正方形有点像
class Solution {
    public int findLength(int[] A, int[] B) {
        int n = A.length, m = B.length;
        //滚动数组优化
        int[][] dp = new int[2][m + 1];//本次的结果只跟上一行有关，那两行之间交替使用数组
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) { //多申请了一个空间，java默认初始化未全0
                                            //从0开始还得处理边界值
            for (int j = m - 1; j >= 0; j--) {
                if(i%2==0) {
                    dp[0][j] = A[i] == B[j] ? dp[1][j + 1] + 1 : 0;
                    //now = (A[i] == B[j]? last+1:0); 这个二维都变化了，不是单纯的一维变化可以一个变量迭代
                    ans = Math.max(ans, dp[0][j]);
                }else{
                    dp[1][j] = A[i] == B[j] ? dp[0][j + 1] + 1 : 0;
                    ans = Math.max(ans, dp[1][j]);
                }
            }
        }
        return ans;
    }
}
